#ifndef _MATRIX
#define _MATRIX

#include <iostream>
#include <iterator>

namespace mylib {
	template<class T> class Matrix {
	public:
		Matrix(size_t _row, size_t _col, const T &val=T());	// constructor _row * _col
		Matrix(const T *_tab);
		~Matrix(){ 
			if( _del_all ) {
				if( _tab )
					delete [] _tab; 
				if( _row_index )
					delete [] _row_index;
				if( _col_index )
					delete [] _col_index;
				_del_all = false;
			}
		}
		class Out_of_range {};
		class Err_input {};
		class Out_of_mem {};

		const T &get(size_t _row, size_t _col)const;	// get information
		Matrix<T> &put(size_t _row, size_t _col, const T &ele);	// write ele to _row*_col
		size_t row()const { return _row; }
		size_t col()const { return _col; }
		void cmps();			// cmps the table
		void write(std::ostream &out);			// output this table
	private :
		Matrix(const Matrix<T> &m) {}			// cannot be copied
		Matrix<T> &operator=(const Matrix<T> &m) {}
	private:
		size_t _row, _col;
		T *_tab;
		size_t *_row_index;				// for compressed matrix
		size_t *_col_index;				// 
		size_t _cmps_row;
		size_t _cmps_col;					// the length of compressed table
		bool _compressed;
		bool _del_all;		// delete allowed
	};
}

// constructor _row * _col
template<class T> mylib::Matrix<T>::Matrix(size_t r, size_t c, const T &val):_row(r),_col(c){
	using namespace std;
	_del_all = true;		// can be deleted
	_row_index=_col_index=0;
	_tab=0;
	_cmps_row = _cmps_col = 0;
	_compressed=false;
	try {
		_tab = new T[_row*_col];
		for(size_t i=0; i < _row*_col; i++ )			// initialize it
			_tab[i] = val;
	} catch(...) {
		Out_of_mem();
	}
}
template<class T> mylib::Matrix<T>::Matrix(const T *t) {			// some need changed??
	_row_index=_col_index=0;
	_del_all = false;					// cannot be deleted
	_cmps_row = _cmps_col = 0;
	_row = *t;
	_col = *++t;
	_compressed = (*++t) ? true : false;
	 if( _row<=0 || _col <= 0 )
		throw Err_input();
	 if( !_compressed ) {
		_tab = const_cast<T *>(++t);		// get the table address
	 } else {
		 t++;
		 _row_index = (size_t *) t;					// set it to row index position
		 t += _row;
		 _col_index = (size_t *) t;
		 t += _col;
		 _cmps_row =  *t;
		 t++;
		 _cmps_col =  *t;
		 t++;
		 _tab = const_cast<T *> (t);
	 }
}
// get information
template<class T> const T &mylib::Matrix<T>::get(size_t r, size_t c) const{
	if( r >= _row || c >= _col )
		throw Out_of_range();
	else if( _compressed ) {
		return _tab[_row_index[r]*_cmps_col+_col_index[c]];
	} else
		return _tab[r*_col+c];
}
// write ele to 
template<class T> mylib::Matrix<T> &mylib::Matrix<T>::put(size_t r, size_t c, const T &ele) {
	if( r >= _row || c >= _col )
		throw Out_of_range();
	else if( !_compressed ){
		_tab[r*_col+c] = ele;
	}
	return *this;
}
template<class T> void mylib::Matrix<T>::write(std::ostream &out){// output this table
	if( !_compressed )
		this->Matrix<T>::cmps();
	out << _row << ", " << _col << ", " << _compressed;
	if( !_compressed ) {
		size_t i=0;
		out << std::endl;
		for(; i < _row; i++ ) {
			for(size_t j=0; j < _col; j++)
				out << ", " << _tab[i*_col+j];
			out << std::endl;
		}
	} else {
		out << std::endl;
		for(size_t i=0; i < _row; i++ )
			out << ", " << _row_index[i];
		out << std::endl;
		for( size_t i=0; i < _col; i++ )
			out << ", " << _col_index[i];
		out << std::endl;
		out << ", " << _cmps_row << ", " << _cmps_col << std::endl;
		for( size_t i=0; i < _cmps_row; i++ ) {
			for( size_t j=0; j < _cmps_col; j++ )
				out  << ", " << _tab[i*_cmps_col+j];
			out << std::endl;
		}
	}
}
#include <list>
#include <set>

namespace cmps_loc {
	template<class T> struct Start_info {
		T *pos;
		size_t num;
	};
}
template<class T> void mylib::Matrix<T>::cmps() {			// cmps the table
	using namespace cmps_loc;
	if( _compressed )
		return;
	try {
		_row_index = new size_t[_row];				// for row index
		_col_index = new size_t[_col];
	} catch(...) {
		if( _row_index ) {
			delete [] _row_index;
			_row_index=0;
		}
		if( _col_index ) {
			delete [] _col_index;
			_col_index=0;
		}
		throw Out_of_mem();
	}
	size_t row_num=0;
	size_t col_num=0;
	std::list<Start_info<T> > rej_set;			// reject set
	std::set<size_t> del_row;
	std::set<size_t> del_col;
	Start_info<T> temp_info;
	for( size_t i=0; i < _row; i++ ) {			// initialize: reject all row
		temp_info.pos = _tab+i*_col;
		temp_info.num = i;
		rej_set.push_back(temp_info);
	}
	while( !rej_set.empty() ) {			// color all the vectex
		typename std::list<Start_info<T> >::iterator R=rej_set.begin();
		Start_info<T> &cur_row = *R;
		_row_index[cur_row.num] = row_num;
		T *cur_pos=cur_row.pos;
		R++;
		while( R!=rej_set.end() ) {			// to color reject vectex
			const Start_info<T> &cmp_row = *R;
			T *cmp_pos=cmp_row.pos;
			size_t i=0;
			for( ; i < _col; i++ )
				if( cur_pos[i] != cmp_pos[i] )
					break;
			if( i >= _col ) {		// same row
				_row_index[cmp_row.num] = row_num;
				del_row.insert(cmp_row.num);			// to label this row has been deleted, colored
				typename std::list<Start_info<T> >::iterator I=R;
				R++;
				rej_set.erase(I);			// delete it
			} else {				// not the same
				R++;			// also reject it
			}
		}
		row_num++;
		rej_set.pop_front();
	}
	for( size_t i=0; i < _col; i++ ) {			// initialize: reject all column
		temp_info.pos = _tab+i;
		temp_info.num = i;
		rej_set.push_back(temp_info);
	}
	while( !rej_set.empty() ) {			// color all the vectex
		typename std::list<Start_info<T> >::iterator R=rej_set.begin();
		const Start_info<T> &cur_col = *R;
		_col_index[cur_col.num] = col_num;
		T *cur_pos=cur_col.pos;
		R++;
		while( R!=rej_set.end() ) {			// to color reject vectex
			const Start_info<T> &cmp_col = *R;
			T *cmp_pos=cmp_col.pos;
			size_t i=0;
			for( ; i < _row; i++ ) {		// compare all row in two columns
				T offset = i*_col;
				if( cur_pos[offset] != cmp_pos[offset] )
					break;
			}
			if( i >= _row ) {		// same column
				_col_index[cmp_col.num] = col_num;
				del_col.insert(cmp_col.num);			// to label this row has been deleted, colored
				typename std::list<Start_info<T> >::iterator I=R;
				R++;
				rej_set.erase(I);			// delete it
			} else {				// not the same
				R++;			// also reject it
			}
		}
		col_num++;
		rej_set.pop_front();
	}
	try {
		T *cmp_tab = new T[row_num*col_num];			// bulid compressed table
		for( size_t i=0; i < _row; i++ ) {
			if( del_row.find(i) != del_row.end() )			// has been deleted
				continue;
			for( size_t j=0; j < _col; j++ ) {
				if( del_col.find(j) != del_col.end() )
					continue;
				cmp_tab[_row_index[i]*col_num+_col_index[j]] = _tab[i*_col+j];
			}
		}
		if( _del_all )
			delete [] _tab;			// delete the old table
		_tab = cmp_tab;
		_del_all=true;
		_compressed=true;
		_cmps_row = row_num;
		_cmps_col = col_num;
	} catch(...) {
		throw Out_of_mem();
	}
}
#endif
